import java.util.Arrays;

/**
 * 时间复杂度：O(N*logN)
 * 空间复杂度：O(N) 所需要申请的空间和原数组的元素个数是一样的
 * 稳定性：稳定
 * 稳定的排序右：归并  冒泡  插入
 */
public class MergeSort {
    //归并的递归写法
    public static void mergeSort(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }

    //归并的非递归
    public static void NorMergeSort(int[] array) {
        int gap = 1;
        while(gap < array.length) {
            //左边递归完之后，left应该往右边走，所以这里应该是i + gap*2
            for(int i = 0; i < array.length; i = i + gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                //mid 和 right 有可能越界
                if(mid >= array.length) {
                    //纠正mid的值，让mid的值趋于合法
                    mid = array.length - 1;
                }
                if(right >= array.length) {
                    right = array.length - 1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }
    private static void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;

        int[] tmpArr = new int[right - left + 1];
        int k = 0;//tmpArr数组的下标

        while(s1 <= e1 && s2 <= e2) {
            if(array[s1] < array[s2]) {
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        //判读不为空的数组，把不为空的数组的内容接到tmpArr数组中
        while(s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }

        while(s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        /**
         * 此时tmpArr数组里面存放的是有序的数据，需要拷贝回原数组
         * 10 6 7 1 3 9 4 2
         * 10 6 7 1  -->下标[0 1 2 3]
         * 3 9 4 2   -->下标[4 5 6 7] 右树不是从0下标开始的
         */

        for(int i = 0; i < k; i++) {
            //i+left
            array[i+left] = tmpArr[i];
        }

    }

    private static void mergeSortFunc(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }

        int mid = (left + right) /2;

        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);

        //此时递归完成，然后合并
        merge(array,left,mid,right);
    }

    public static void main(String[] args) {
        int[] array = {10,6,7,1,3,9,4,2};
        NorMergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
